N-queens II

Time: O(N!); Space: O(N); hard

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: 4

Output: 2

Explanation:

  • There are two distinct solutions to the 4-queens puzzle as shown below.

    [
 [". Q . .",  // Solution 1
  ". . . Q",
  "Q . . .",
  ". . Q ."],

 [". . Q .",  // Solution 2
  "Q . . . ",
  ". . . Q",
  ". Q . ."]
]

Example 2:

Input: n = 1

Output: 1

[7]:

from functools import reduce
class Solution1(object):
    """
    Time: O(N!)
    Space: O(N)
    """
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.cols = [False] * n
        self.main_diag = [False] * (2 * n)
        self.anti_diag = [False] * (2 * n)
        return self.totalNQueensRecu([], 0, n)

    def totalNQueensRecu(self, solution, row, n):
        if row == n:
            return 1
        result = 0
        for i in range(n):
            if not self.cols[i] and not self.main_diag[row + i] and not self.anti_diag[row - i + n]:
                self.cols[i] = self.main_diag[row + i] = self.anti_diag[row - i + n] = True
                result += self.totalNQueensRecu(solution + [i], row + 1, n)
                self.cols[i] = self.main_diag[row + i] = self.anti_diag[row - i + n] = False
        return result

[8]:

s = Solution1()
n = 4
assert s.totalNQueens(n) == 2
n = 1
assert s.totalNQueens(n) == 1

[11]:

class Solution2(object):
    """
    Solution2lower solution
    """
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        return self.totalNQueensRecu([], 0, n)

    def totalNQueensRecu(self, solution, row, n):
        if row == n:
            return 1
        result = 0
        for i in range(n):
            if i not in solution and reduce(lambda acc, j: \
                        abs(row - j) != abs(i - solution[j]) \
                        and acc, range(len(solution)), True):
                result += self.totalNQueensRecu(solution + [i], row + 1, n)
        return result

[12]:

s = Solution2()
n = 4
assert s.totalNQueens(n) == 2
n = 1
assert s.totalNQueens(n) == 1